#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
    摩尔投票法
"""

class Solution:
    """
    @param: nums: a list of integers
    @return: find a  majority number
    """
    def majorityNumber(self, nums):
        if not nums:
            return None

        maj = nums[0]
        cnt = 1

        for i in nums[1:]:
            if i == maj:
                cnt += 1
            else:
                cnt -= 1

            if cnt <= 0:
                maj = i

        return maj


def main():
    print("start main")

if __name__ == "__main__":
    main()
